/**
 * 
 */
package array.passed;

import utils.CreateUtils;
import utils.HelpUtils;
import utils.PrintUtils;

/**
 * @author Michael

 * Given an unsorted integer array, find the first missing positive integer.
 * For example,
 * Given [1,2,0] return 3,
 * and [3,4,-1,1] return 2.
 * Your algorithm should run in O(n) time and uses constant space.
 */
public class FindFirstMissingPositive {

	public int firstMissingPositive(int[] A) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (A == null || A.length == 0)
			return 1;

		for (int i = 0; i < A.length; i++) {
			while (A[i] > 0 && A[i] <= A.length && A[i] != A[A[i] - 1]) {
				swap(A, i, A[i] - 1);
			}
		}

		for (int i = 0; i < A.length; i++) {
			if (A[i] != i + 1)
				return i + 1;
		}

		return A.length + 1;
	}

	private void swap(int[] A, int i, int j) {
		if (i == j)
			return;
		A[i] = A[i] ^ A[j];
		A[j] = A[i] ^ A[j]; // i ^ j ^ j
		A[i] = A[i] ^ A[j]; // i ^ j ^ i ^ j ^ j
	}

	/*
	 * 0 1 2 3, 4 
	 * [4, -1, 100, 3, 1] 
	 * [1, -1, 100, 3, 4]
	 */
	public static int find(int[] arr) {
		assert arr != null && arr.length >= 0;

		for (int i = 0; i < arr.length; ++i) {
			while (arr[i] > 0 && arr[i] <= arr.length
					&& arr[i] != arr[arr[i] - 1]) {
				HelpUtils.swap(arr, i, arr[i] - 1);
			}
		}

		for (int i = 0; i < arr.length; ++i) {
			if (arr[i] != i + 1) {
				return i + 1;
			}
		}

		return arr.length + 1;
	}

	/* alternative */
	public static int find1(int[] a) {
		for (int i = 0; i < a.length; i++) {
			while (a[i] != i + 1) {
				if (!(a[i] <= 0 || a[i] > a.length || a[i] == a[a[i] - 1])) {
					int temp = a[i];
					a[i] = a[temp - 1];
					a[temp - 1] = temp;
				} else {
					break;
				}
			}
		}

		for (int i = 0; i < a.length; i++) {
			if (a[i] != i + 1)
				return i + 1;
		}
		return a.length + 1;
	}

	public static int find2(int[] arr) {
		if (arr == null || arr.length == 0)
			return 1;

		for (int i = 0; i < arr.length; ++i) {
			while (arr[i] > 0 && arr[i] <= arr.length
					&& arr[i] != arr[arr[i] - 1]) {
				HelpUtils.swap(arr, i, arr[i] - 1);
			}
		}

		for (int i = 0; i < arr.length; ++i) {
			if (arr[i] != i + 1) {
				return i + 1;
			}
		}

		return arr.length + 1;
	}

	/**
	 * 
	 */
	public FindFirstMissingPositive() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = CreateUtils.randIntArray(10, 10);
		PrintUtils.printArray(a);
		System.out.println(find(a));

		int[] arr1 = { 0, -1, 3, 1 };
		System.out.printf("Frist missing is %d\n",
				FindFirstMissingPositive.find2(arr1));

		int[] arr2 = { 0, 1, 2, 3, 6 };
		System.out.printf("Frist missing is %d\n",
				FindFirstMissingPositive.find2(arr2));

		int[] arr3 = { -1, -2, -3, 1 };
		System.out.printf("Frist missing is %d\n",
				FindFirstMissingPositive.find2(arr3));

		int[] arr4 = { 1, 2, 3, 5, 4 };
		System.out.printf("Frist missing is %d\n",
				FindFirstMissingPositive.find2(arr4));
	}

}
